{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Keypresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumKeypresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少按键次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个 9 键键盘，按键按 1 到 9 编号，每个按键对应着几个英文小写字母。你可以决定每个按键对应哪些英文字母，但要满足如下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>26 个英文小写字母必须全部映射到这 9 个按键上。</li>\n",
    "\t<li>每个英文字母只能映射到 <strong>恰好</strong> 一个按键上。</li>\n",
    "\t<li>每个按键 <strong>最多</strong> 对应 3 个英文字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果想打出按键上的第一个字母，只需要按一次。如果想打出按键上的第二个字母，则需要按两次，依次类推。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，返回基于你设计的键盘打出 <code>s</code> 需要的<strong> 最少</strong> 按键次数。</p>\n",
    "\n",
    "<p><b>注意：</b>字母映射到每个按键上，映射的顺序无法进行更改。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/05/image-20220505184346-1.png\" style=\"width: 300px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"apple\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>上图所示为设置键盘的最佳方法之一。\n",
    "按按键 1 一次输入 'a' 。\n",
    "按按键 6 一次输入 'p' 。\n",
    "按按键 6 一次输入 'p' 。\n",
    "按按键 5 一次输入 'l' 。\n",
    "按按键 3 一次输入 'e' 。\n",
    "总共按按键 5 次，所以返回 5 。</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/05/image-20220505203823-1.png\" style=\"width: 300px; height: 288px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcdefghijkl\"\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>上图所示为设置键盘的最佳方法之一。\n",
    "字母 'a' 到 'i' 每个只需要按一次按键。\n",
    "按按键 1 两次输入 'j' 。\n",
    "按按键 2 两次输入 'k' 。\n",
    "按按键 3 两次输入 'l' 。\n",
    "总共按按键 15 次，所以返回 15 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-keypresses](https://leetcode.cn/problems/minimum-number-of-keypresses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-keypresses](https://leetcode.cn/problems/minimum-number-of-keypresses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"apple\"', '\"abcdefghijkl\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        ans = 0\n",
    "        for i, v in enumerate(sorted(cnt.values(), reverse=True)):\n",
    "            ans += v * (i // 9 + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        count = Counter(s)\n",
    "        vlist = list(count.values())\n",
    "        vlist.sort(reverse=True)\n",
    "        res = 0\n",
    "        for i,v in enumerate(vlist):\n",
    "            res += (i//9+1)*v\n",
    "        return res\n",
    "   \n",
    "    def minimumKeypresses0(self, s: str) -> int:\n",
    "        counter=collections.Counter(s)\n",
    "        sorted_counter = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)\n",
    "        #print(sorted_counter)\n",
    "        res=0\n",
    "\n",
    "        for i, ele in enumerate(sorted_counter):\n",
    "            res+=(i//9+1)*ele[1]\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：jliang2010\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-keypresses/solutions/1485806/xian-tong-ji-mei-ge-zi-fu-de-shu-liang-b-ek7a/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        table = {}\n",
    "        for c in s:\n",
    "            table.setdefault(c,0)\n",
    "            table[c] += 1\n",
    "        table = list(table.items())    \n",
    "        table.sort(key=lambda x:x[1],reverse=True)\n",
    "        index = 0\n",
    "        n = len(table)\n",
    "        ans = 0\n",
    "        while index < n:\n",
    "            ans += table[index][1] * (index // 9 + 1)\n",
    "            index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        cnt=Counter(s)\n",
    "        ans,temp,arr=0,0,0\n",
    "        res=list(cnt.values())\n",
    "        res.sort(key=lambda x:-x)\n",
    "        for i in res:\n",
    "            if arr==0:\n",
    "                temp+=1\n",
    "            arr=(arr+1)%9\n",
    "            ans+=temp*i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            d[c] += 1\n",
    "\n",
    "        l = list(d.values())\n",
    "        l.sort(reverse=True)\n",
    "        arr = [9, 9, 8]\n",
    "        ret = 0\n",
    "        for v in l:\n",
    "            if arr[0] > 0:\n",
    "                arr[0] -= 1\n",
    "                ret += v\n",
    "            elif arr[1] > 0:\n",
    "                arr[1] -= 1\n",
    "                ret += 2 * v\n",
    "            else:\n",
    "                ret += 3 * v\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        cnt=Counter(s)\n",
    "        ans,temp,arr=0,0,0\n",
    "        res=sorted(cnt.values(),key=lambda x:-x)\n",
    "        for i in res:\n",
    "            if arr==0:\n",
    "                temp+=1\n",
    "            arr=(arr+1)%9\n",
    "            ans+=temp*i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        return sum(x * (1 + i // 9) for i, (_, x) in enumerate(Counter(s).most_common()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        counter=collections.Counter(s)\n",
    "        sorted_counter = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)\n",
    "        #print(sorted_counter)\n",
    "        res=0\n",
    "\n",
    "        for i, ele in enumerate(sorted_counter):\n",
    "            res+=(i//9+1)*ele[1]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        counter=collections.Counter(s)\n",
    "        sorted_counter = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)\n",
    "        #print(sorted_counter)\n",
    "        res=0\n",
    "\n",
    "        for i, ele in enumerate(sorted_counter):\n",
    "            res+=(i//9+1)*ele[1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        l = [0] * 26\n",
    "        ord_a = ord('a')\n",
    "        for c in s:\n",
    "            ord_c = ord(c)\n",
    "            l[ord_c - ord_a] += 1\n",
    "\n",
    "        l.sort(reverse=True)\n",
    "        arr = [9, 9, 8]\n",
    "        ret = 0\n",
    "        for v in l:\n",
    "            if arr[0] > 0:\n",
    "                arr[0] -= 1\n",
    "                ret += v\n",
    "            elif arr[1] > 0:\n",
    "                arr[1] -= 1\n",
    "                ret += 2 * v\n",
    "            else:\n",
    "                ret += 3 * v\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from heapq import heapreplace\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        # 使用 Counter 统计每个字母的出现次数\n",
    "        cnt = Counter(s)\n",
    "        # 初始化一个最小堆，用于维护每个按键需要的按键次数\n",
    "        h = [1 for _ in range(9)]\n",
    "        # 初始化结果为0\n",
    "        ans = 0\n",
    "        # 遍历每个字母，优先分配给需要按键次数少的按键\n",
    "        for v in sorted(cnt.values(), key=lambda x: -x):\n",
    "            # 如果当前需要按键次数最少的按键次数少于3\n",
    "            if h[0] < 3:\n",
    "                # 分配字母给这个按键，并更新这个按键需要的按键次数\n",
    "                ans += v * heapreplace(h, h[0] + 1)\n",
    "            else:\n",
    "                # 如果所有按键都需要按键次数为3，就分配给当前需要按键次数最少的按键\n",
    "                ans += v * h[0]\n",
    "        # 返回结果\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        cnt=collections.Counter(s)\n",
    "        arr=cnt.most_common()\n",
    "        i=0\n",
    "        vlaue=collections.Counter()\n",
    "        tmp=1\n",
    "       \n",
    "        for x in arr:\n",
    "            vlaue[x[0]]=tmp\n",
    "            i=i+1\n",
    "            if i==9:\n",
    "                i=0\n",
    "                tmp+=1\n",
    "        ans=0\n",
    "        for x in s:\n",
    "            ans+=vlaue[x]\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minimumKeypresses(self, s: str) -> int:\n",
    "    #     count = Counter(s)\n",
    "    #     ch = [k for k in count.keys()]\n",
    "    #     sorted(ch, key = lambda k:-count[k])\n",
    "    #     res = 0\n",
    "    #     for i,c in enumerate(ch):\n",
    "    #         res += (i//9+1)*count[c]\n",
    "    #     return res\n",
    "    # ?????????\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        counter=collections.Counter(s)\n",
    "        sorted_counter = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)\n",
    "        #print(sorted_counter)\n",
    "        res=0\n",
    "\n",
    "        for i, ele in enumerate(sorted_counter):\n",
    "            res+=(i//9+1)*ele[1]\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：jliang2010\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-keypresses/solutions/1485806/xian-tong-ji-mei-ge-zi-fu-de-shu-liang-b-ek7a/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        counter = sorted(Counter(s).items(), key=lambda x: x[1], reverse=True)\n",
    "        pq = [1] * 9\n",
    "        heapq.heapify(pq)\n",
    "        res = 0\n",
    "        for c, f in counter:\n",
    "            cur = heapq.heappop(pq)\n",
    "            res += cur * f\n",
    "            if cur + 1 <= 3:\n",
    "                heapq.heappush(pq, cur + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        table = {}\n",
    "        for c in s:\n",
    "            table.setdefault(c,0)\n",
    "            table[c] += 1\n",
    "        table = list(table.items())    \n",
    "        table.sort(key=lambda x:x[1],reverse=True)\n",
    "        index = 0\n",
    "        n = len(table)\n",
    "        ans = 0\n",
    "        while index < n:\n",
    "            ans += table[index][1] * (index // 9 + 1)\n",
    "            index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        counter=collections.Counter(s)\n",
    "        sorted_counter = sorted(counter.items(), key=lambda kv: kv[1], reverse=True)\n",
    "        res=0\n",
    "        for i, ele in enumerate(sorted_counter):\n",
    "            res+=(i//9+1)*ele[1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from heapq import heapreplace\n",
    "\n",
    "class Solution:\n",
    "    def minimumKeypresses(self, s: str) -> int:\n",
    "        cnt = Counter(s)  # 步骤1：统计字符频次\n",
    "        h = [1 for _ in range(9)]  # 步骤2：初始化堆\n",
    "        ans = 0  # 初始化总按键次数为0\n",
    "\n",
    "        # 步骤3和4：排序并分配字符到按键\n",
    "        for v in sorted(cnt.values(), key=lambda x: -x):\n",
    "            if h[0] < 3:  # 如果堆顶元素（即当前最少使用次数的按键）使用次数少于3\n",
    "                ans += v * heapreplace(h, h[0] + 1)  # 分配字符到这个按键，并更新按键使用次数\n",
    "            else:  # 如果所有按键都已经使用了3次\n",
    "                ans += v * h[0]  # 使用当前最少使用次数的按键\n",
    "\n",
    "        return ans  # 步骤5：返回总按键次数\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
